package com.pan.alg.niuke.stackque;

import org.checkerframework.checker.units.qual.A;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 描述
 * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
 * 数据范围：
 * 0\le k,n \le 100000≤k,n≤10000，
 * 数组中每个数的大小0 \le val \le 10000≤val≤1000
 *
 * 要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogk)O(nlogk)
 */
public class GetLeastNumbersSolution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k<=0){
            return new ArrayList<>();
        }

        ArrayList<Integer> leastNumber = new ArrayList<>();

        sortInput(input);

        return leastNumber;
    }

    private void sortInput(int[] input) {


    }

    private void partion(int[] input,int l,int r){
        int tmp = input[l];



    }

    private void swap(int[] input, int l, int r) {
        int tmp = input[l];
        input[l]=input[r];
        input[r]=tmp;
    }

    private void putNumIn(ArrayList<Integer> leastNumber, int value,int k) {
        int size = leastNumber.size();
        if(size <=k){
            for (int i = 0; i < size; i++) {
                int tmp = leastNumber.get(i);
                if(tmp>value){
                    leastNumber.add(i,tmp);
                }
            }

        }else{

        }

    }

    public static void main(String[] args) {
        int[] nums = {5,1,6,5,9,3,4};
        GetLeastNumbersSolution getLeastNumbersSolution = new GetLeastNumbersSolution();
        getLeastNumbersSolution.sortInput(nums);
        System.out.println(String.format("%s,",Arrays.asList(nums)));
    }


}
